package com.cf.edu181;

import java.io.*;

public class b {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            String[] s = br.readLine().split(" ");
            long a = Long.parseLong(s[0]);
            long b = Long.parseLong(s[1]);
            long k = Long.parseLong(s[2]);

            if (a <= k && b <= k) {
                out.println(1);
                continue;
            }
            long x = gcd(a, b);
            if (x > 1 && a / x <= k && b / x <= k) {
                out.println(1);
                continue;
            }
            out.println(2);
        }
        out.close();
        out.close();
        br.close();
    }

    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

}
